package com.LeeCode;

import java.util.*;

/**
 * 删除星号以后字典序最小的字符串
 */

public class Code3170 {
    public static void main(String[] args) {
        String s = "acba**";
        System.out.println(new Code3170().clearStars(s));
    }

    public String clearStars(String s) {
        Deque<Integer>[] stacks = new Deque[26];
        Arrays.setAll(stacks, i -> new ArrayDeque<>());

        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != '*') {
                stacks[chars[i] - 'a'].push(i);
                continue;
            }

            for(Deque<Integer> stack : stacks) {
                if(!stack.isEmpty()){
                    int index = stack.pop();
                    chars[index] = '*';
                    break;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(char c : chars) {
            if(c != '*'){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
